题解 P3254 【圆桌问题】

发表于 | 更新于

$Description$

假设有来自$m$个不同单位的代表参加一次国际会议。每个单位的代表数分别为$r_i(1\leqslant i\leqslant m)$。

会议餐厅共有$n$张餐桌，每张餐桌可容纳$c_i(1\leqslant i\leqslant n)$个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。

$Solution$

贪心做法

把桌子和单位的规模分别从大到小排个序(其实桌子拍不拍序没什么影响)。因为单位规模越大就越难满足，所以我们优先考虑他们;

而对于桌子你可以这样想，你桌子数量越多显然更容易满足题意，又因为小桌子很快会坐满而导致不能用，所以我们优先坐大桌子。

还有一种最大流的做法

考虑对桌子和单位构点。从源点连容量为$r_i$的边到单位$i$，从餐桌$i$连容量为$c_i$的边到汇点。

注意到每个单位只能在每张桌子上放一个人。考虑从每个单位向每张桌子连一条容量为$1$的边。

如果最大流小于人数和则无解。

否则对于每个单位，枚举它的出边，输出满流边的终点即可。

$Code$

只贴了贪心的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define pb push_back
#define N 400
using namespace std;
struct node{
    int w,id;
}p[N],q[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
vector<int>v[400];
inline bool cmp(node a,node b){
    return a.w>b.w;
}
int ans[N];
signed main(){
    int n=read(),m=read();
    for (int i=1;i<=n;++i)p[i].w=read(),p[i].id=i;
    for (int i=1;i<=m;++i)q[i].w=read(),q[i].id=i;
    sort(p+1,p+1+n,cmp);
    sort(q+1,q+1+m,cmp);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=p[i].w;++j){
            if (!q[j].w){puts("0");return 0;}
            v[i].pb(q[j].id);--q[j].w;
        }
        sort(q+1,q+1+m,cmp);
        ans[p[i].id]=i;
    }
    puts("1");
    for (int i=1;i<=n;++i,puts(""))
        for (int j=0;j<v[ans[i]].size();++j)
            printf("%d ",v[ans[i]][j]);
    return 0;
}